package MyDFS;

import com.sun.deploy.util.SyncAccess;

import java.util.ArrayList;
import java.util.List;

/**
 * 784. 字母大小写全排列
 *
 * 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
 *
 *
 *
 * 示例：
 * 输入：S = "a1b2"
 * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 */
public class Leetcode0784 {
    public static  List<String> letterCasePermutation(String S) {
        List<String> res = new ArrayList<>();
        int len = S.length();
        boolean used[] = new boolean[len];
        int count = 0;
        for(int ss=0; ss<S.length(); ss++){
            if(!Character.isLetter(S.charAt(ss))){
                used[ss] = true;
                count ++;
            }
        }
        for(boolean ssss : used){
            System.out.print(ssss + " ");
        }
        System.out.println();
        System.out.println(count);
        dfs(S, len, len - count, 0, 0, used, "", res);
        return res;
    }
    public static void dfs(String S, int len, int count,int cnt, int index, boolean used[], String path, List<String> res){
        if(cnt >= count){
            int cur = index;
            while(cur < len){
                path += S.charAt(cur);
                cur ++;
            }
            res.add(path);
            System.out.println(path);
            return;
        }

        int cur = index;
        String newPath = new String(path);

        while(cur < len){
            if(!Character.isLetter(S.charAt(cur))){
                newPath += S.charAt(cur);
            }
            if(Character.isLetter(S.charAt(cur))){
                boolean newUsed[] = new boolean[len];
                System.arraycopy(used,0,newUsed,0,len);
                newUsed[cur] = true;

                String newPath1 = newPath + Character.toLowerCase(S.charAt(cur));
                dfs(S, len, count, cnt +1, cur+1, newUsed, newPath1, res);

                String newPath2 = newPath + Character.toUpperCase(S.charAt(cur));
                dfs(S, len, count, cnt +1, cur+1, newUsed, newPath2, res);

                return;
            }
            cur ++;
        }
    }

    public static void main(String[] args) {
        String ss = "a1b2c3243";
        letterCasePermutation(ss);
    }
}
